package com.hr.剑指offer.work1;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author 周恒哲
 * @date 2020/06/17
 **/
public class 面试题40_最小的k个数 {
    //调用api
    public static int[] getLeastNumbers(int[] arr, int k) {
        Arrays.sort(arr);
        int[] res=new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=arr[i];
        }
        return res;
    }
    /**
     * 最大堆
     * 算法的复杂度分析：
     *
     * 由于使用了一个大小为 k 的堆，空间复杂度为 O(k)O(k)；
     * 入堆和出堆操作的时间复杂度均为 O(\log k)O(logk)，每个元素都需要进行一次入堆操作，
     * 故算法的时间复杂度为 O(n \log k)O(nlogk)。
     */

    public static int[] getLeastNumbers2(int[] arr, int k) {
        if (k==0){
            return new int[0];
        }
        // 使用一个最大堆（大顶堆）
        // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
        Queue<Integer> queue=new PriorityQueue<>(k,(i1,i2)->Integer.compare(i2,i1));;
        for (int num:arr) {
            // 当前数字小于堆顶元素才会入堆
            if (queue.isEmpty()||queue.size()<k || num<queue.peek()){
                queue.offer(num);
            }
            if (queue.size()>k){
                queue.poll();// 删除堆顶最大元素
            }
        }
        // 将堆中的元素存入数组
        int[] res=new int[queue.size()];
        int j=0;
        for (int num:queue) {
            res[j++]=num;
        }
        return res;
    }

    public static void main(String[] args) {

    }
}
